class MinHeap {
    constructor() {
        this.heap = [];
    };
    getLeftIndex(index) {
        return 2 * index + 1
    };
    getRightIndex(index) {
        return 2 * index + 2
    };
    getParentIndex(index) {
        if (index == 0) {
            return undefined;
        } else {
            return Math.floor((index - 1) / 2);
        }
    };
    // 插入数值
    insert(value) {
        if (value != null) {
            this.heap.push(value);
            this.siftUp(this.heap.length - 1);
            return true;
        } else {
            return false;
        }
    };
    siftUp(index) {
        let parent = this.getParentIndex(index);
        while (index > 0 && this.heap[parent] > this.heap[index]) {
            this.swap(this.heap, parent, index);
            index = parent;
            parent = this.getParentIndex(index);
        }
    };
    swap(array, a, b) {
        const temp = array[a];
        array[a] = array[b];
        array[b] = temp
    };

    size() {
        return this.heap.length;
    };
    isEmpty() {
        return this.size() === 0;
    };
    findMinimum() {
        return this.isEmpty() ? undefined : this.heap[0];
    };

    extract() {
        if (this.isEmpty()) {
            return undefined;
        } else if (this.size()) {
            return this.heap.shift();
        } else {
            const removeValue = this.heap.shift();
            this.siftDown(0);
            return removeValue;
        }
    };
    siftDown(index) {
        let element = index;
        const left = this.getLeftIndex(index);
        const right = this.getRightIndex(index);
        const size = this.size();
        if (left < size && this.heap[element] > this.heap[left]) {
            element = left;
        };
        if (right < size && this.heap[element] > this.heap[right]) {
            element = right;
        };
        if (index !== element) {
            this.swap(this.heap, index, element);
            this.siftDown(element)
        }
    }
}

class MaxHeap {
    constructor() {
        this.heap = [];
    };
    getLeftIndex(index) {
        return 2 * index + 1
    };
    getRightIndex(index) {
        return 2 * index + 2
    };
    getParentIndex(index) {
        if (index == 0) {
            return undefined;
        } else {
            return Math.floor((index - 1) / 2);
        }
    };
    // 插入数值
    insert(value) {
        if (value != null) {
            this.heap.push(value);
            this.siftUp(this.heap.length - 1);
            return true;
        } else {
            return false;
        }
    };
    siftUp(index) {
        let parent = this.getParentIndex(index);
        while (index > 0 && this.heap[parent] < this.heap[index]) {
            this.swap(this.heap, parent, index);
            index = parent;
            parent = this.getParentIndex(index);
        }
    };
    swap(array, a, b) {
        const temp = array[a];
        array[a] = array[b];
        array[b] = temp
    };

    size() {
        return this.heap.length;
    };
    isEmpty() {
        return this.size() === 0;
    };
    findMaximum() {
        return this.isEmpty() ? undefined : this.heap[0];
    };

    extract() {
        if (this.isEmpty()) {
            return undefined;
        } else if (this.size()) {
            return this.heap.shift();
        } else {
            const removeValue = this.heap.shift();
            this.siftDown(0);
            return removeValue;
        }
    };
    siftDown(index) {
        let element = index;
        const left = this.getLeftIndex(index);
        const right = this.getRightIndex(index);
        const size = this.size();
        if (left < size && this.heap[element] < this.heap[left]) {
            element = left;
        };
        if (right < size && this.heap[element] < this.heap[right]) {
            element = right;
        };
        if (index !== element) {
            this.swap(this.heap, index, element);
            this.siftDown(element)
        }
    }
};

const arr1 = new MaxHeap();
arr1.insert(2);
arr1.insert(3);

arr1.insert(1);
console.log(arr1.findMaximum());